The present invention relates to the rendering of three-dimensional objects in a computer system, graphics display system, or other system for rendering or printing out the scene or objects.
In conventional graphics systems, an object or scene is scanned an image of it is otherwise digitized and stored in the system as a set of data points relating to position, texture, and color. The scanned image is tessellated into sets of object elements such as polygons (typically triangles), which in the aggregate approximate the shape of the original object or scene (generally, the geometry) to the degree of resolution of the imaging and storage properties of the system.
For high-quality (high-resolution) images, as are used for example in CAD applications or molecular modeling, it has been a challenge to current systems to render the stored scenes quickly enough to make real-time motion or viewpoint alteration practical. Instead compromises have been necessary, such as either simplifying the image by reducing it to wire-frame drawings, eliminating the texture and/or simplifying the color content, or accepting a very slow rate in order to achieve high-resolution rendering.
In conventional systems, a scene is rendered (such as on a monitor, or printed on a printer) by reading the image (or "geometry") data file into the system, and rendering the triangles as a series of scan lines on the monitor or other display or image output device. The data file may be in any of a number of different conventional formats, such as in the xgl.sub.-- triangle.sub.-- list (xgl.sub.-- multi.sub.-- simple.sub.-- polygon) format, which is a standardly used format among workstation manufacturers. For a discussion of a conventional such procedure for polygon representation in data files, see Foley, van Dam, et al., Computer Graphics/Principles and Practice, pp. 473 et seq. (Addison Wesley, 2d Ed. 1987)
When the image read into the rendering system (such as in the format of a list of triangles), it is then processed in a standard procedure as illustrated by the flow chart of FIG. 1. The steps 10-110 indicated in this flow chart are standard in the field of computer graphics. A discussion of object rendering may be found, for example, in the aforementioned Computer Graphics/Principles and Practice, at pages 806 et seq. A system for rendering three-dimensional images in a fashion similar to that of FIG. 1 is discussed, for example, in the article "Leo: A System for Cost Effective 3D Shaded Graphics", COMPUTER GRAPHICS Proceedings, Annual Conference Series (1993). Each of the foregoing publications is incorporated herein by reference.
One of the steps carried out by a graphics driver in the process of rendering a scene is that of face determination (see box 40 in FIG. 1). This includes determining whether a given triangle's predefined "front" face is visible from a particular point of view selected by the user. The "front" face is defined in advance by the particular rendering system by, for example, a vector normal to the surface of the triangle, with the direction of the vector (and hence the direction of the front face) being determined by a right-hand (or, optionally, left-hand) rule traversing the three vertices of the triangle in an order determined by the manner in which they are stored in the triangle's data structure. For instance, in FIG. 1A, the three points 200-220 determine the direction of the normal vector 230, and hence the side of the triangle 205 that is to be defined as the front face 240.
In general, there may be three components to the face determination step, all of which may be selected by the user: (1) face distinguishing, meaning applying different attributes (such as color) to the front faces than to the back faces; (2) culling of the front- or back-facing triangles; and (3) flipping of normals of the triangles.
Face distinguishing is a technique particularly used in molecular imaging or medical imaging systems to render multiple surfaces of a scene. In other types of systems (such as MCAD), the invisible faces may simply be culled out.
In prior systems, the graphics driver maintains the list (or "strip") of triangles as a single entity, and thus performs calculations for face culling and face distinguishing on each one of the triangles. This involves both intensive processor usage and heavy memory access to the image file. It would be preferable to arrive at a system that could intelligently determine which triangles are to be rendered for display, and preferentially access and process those triangles.
Another characteristic of current systems is that they process front- and back-facing triangles in the order in which they are accessed in the triangle lists. While this is a simple approach, it can be inefficient because it results in repeated memory accesses to the image file, leading to memory access being a bottleneck for the rendering procedure. It would therefore be useful to provide a system wherein the memory accesses are made more efficient by advance determination of which triangles should be rendered, and in which order. A procedure for making such a determination is needed.
When triangles are accessed as noted, in the order in which they are stored (intermixed front- and back-facing) in the object data file, and a procedure such as that shown in FIG. 1 is used, the transformation of vertices of the triangles (see box 20) from model space (i.e. the data file's reference coordinate system) into device space (i.e. the display or screen coordinate system) takes place before the step of face determination (see box 40), and hence before it is determined whether the triangle being transformed is even to be visible on the screen for the selected viewpoint. For instance, if back culling is selected, then none of the back-facing triangles should be shown, and any processor time taken in transformation of the vertices of back-facing triangles is squandered. Since vertex transformation is a very processor-intensive, time-consuming procedure, such an approach is wasteful of resources and slows down the rendering process.